package com.xj.algorithm.leetcode;

/**
 * 相同的树
 */
public class L100_判断两个树是否相同 {

    /**
     *给定两个二叉树，编写一个函数来检验它们是否相同。
     *
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * 示例 1:
     * 输入:       1         1
     *           / \       / \
     *          2   3     2   3
     *
     *         [1,2,3],   [1,2,3]
     *
     * 输出: true
     *
     * 示例 2:
     * 输入:      1          1
     *           /           \
     *          2             2
     *
     *         [1,2],     [1,null,2]
     *
     * 输出: false
     *
     * 示例 3:
     * 输入:       1         1
     *           / \       / \
     *          2   1     1   2
     *
     *         [1,2,1],   [1,1,2]
     *
     * 输出: false
     */
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        System.out.println(isSameTreeOffice(treeNode,treeNode));

        TreeNode treeNode2=new TreeNode(1);
        treeNode2.left=new TreeNode(2);

        TreeNode treeNode3=new TreeNode(1);
        treeNode3.right=new TreeNode(2);
        System.out.println(isSameTreeOffice(treeNode2,treeNode3));

        TreeNode treeNode4=new TreeNode(1);
        treeNode4.left=new TreeNode(2);
        treeNode4.right=new TreeNode(1);

        TreeNode treeNode5=new TreeNode(1);
        treeNode5.left=new TreeNode(1);
        treeNode5.right=new TreeNode(2);
        System.out.println(isSameTreeOffice(treeNode4,treeNode5));
    }

    //自己的解法：所有有节点的地方，值都相同。使用深度遍历，也就是根左右的方式
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!=null && q!=null){
            if(p.val!=q.val){
                return false;
            }
            if(!isSameTree(p.left,q.left)){
                return false;
            }
            if(!isSameTree(p.right,q.right)){
                return false;
            }
        }else if(p==null && q!=null){
            return false;
        }else if(p!=null && q==null){
            return false;
        }
        return true;
    }

    //官方解法：递归算法
    public static boolean isSameTreeOffice(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTreeOffice(p.right, q.right) && isSameTreeOffice(p.left, q.left);
    }
}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}
